//
// Created by Jisam on 2024/7/26 23:19.
// solve c
#include <bits/stdc++.h>

#define PSI pair<string,int>
#define PII pair<int,int>
#define PDI pair<double,int>
#define PDD pair<double,double>
#define VVI vector<vector<int>>
#define VI vector<int>
#define VS vector<string>

#define PQLI priority_queue<int, vector<int>, less<int>>
#define PQGI priority_queue<int, vector<int>, greater<int>>
#define i64 long long

using namespace std;

const int N = 1e5 + 5;
i64 ans;

void solve() {
    int n, q, l, r;
    cin >> n >> q;
    string a, b;
    cin >> a >> b;

    for (int i = 0; i < q; i++) {
        cin >> l >> r;
        map<char, int> ma, mb;
        int cnt = 0;
        for (int k = l; k <= r; k++) {
            ma[a[k - 1]]++;
            mb[b[k - 1]]++;
        }
//        for (auto [x, y]: ma) {
//            cout << x <<" " << y << " ";
//        }
//        cout <<"\n";
//        for (auto [x, y]: mb) {
//            cout << x <<" " << y << " ";
//        }
//        cout <<"\n";
        if(ma.size() == 2 && mb.size() == 2){
            int f = 1;
            for(auto [x,y] : ma){
                if(f){
                    f = 0;
                    cnt += y;
                }else{
                    cnt -= y;
                }
            }
            cnt = abs(cnt);
        }else{
            for (auto [x, y]: ma) {
                if (mb.find(x) != mb.end() && mb[x] != ma[x]) {
                    cnt += min(ma[x], mb[x]);
                }
                if (mb.find(x) == mb.end()) {
                    cnt += ma[x];
                }
            }
        }

        cout << cnt << "\n";
    }

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--) solve();
//    cout << "\n"[];
    return 0;
}